The present invention relates to computer processing, and more specifically, to branch prediction methods in computer processing.
Branch prediction is used to enhance the performance of modern processors. When a processor detects a conditional branch, an uncertainty is temporarily introduced into the pipeline of the processor. If the branch is taken, the next instruction is fetched from an address usually specified in the branch instruction. If the branch is not taken, execution proceeds to the instruction following the branch.
Large amounts of chip area are usually dedicated to the branch prediction mechanism in a processor. In practice, the branch address and target address of each branch encountered by the processor are saved in a table, typically called a Branch History Table (BHT). During the instruction fetch phase of a processing pipeline, the BHT is searched for a matching branch address, and if found, its target is fetched and the instruction located at this address becomes the next instruction decoded. If no matching branch address is found in the instruction fetch segment, instruction fetching and decoding continue down the sequential path. Branch prediction errors occur when the table is incorrect and corrections to the table are implemented.
Prefetching is a commonly used tool to reduce cache miss delays and improve cache hit ratios. Prefetching is also used as a technique to reduce the delays caused by branch prediction errors. Branch-prediction prefetching attempts to anticipate which parts of a program will be used in the near future and prefetches information that describes the upcoming branch into the branch predictor.